import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行
 *
 * 示例：
 * 输入
 * ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
 * [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
 * 输出
 * [null, null, null, 1, null, -1, null, -1, 3, 4]
 * 解释
 * LRUCache lRUCache = new LRUCache(2);
 * lRUCache.put(1, 1); // 缓存是 {1=1}
 * lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
 * lRUCache.get(1);    // 返回 1
 * lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
 * lRUCache.get(2);    // 返回 -1 (未找到)
 * lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
 * lRUCache.get(1);    // 返回 -1 (未找到)
 * lRUCache.get(3);    // 返回 3
 * lRUCache.get(4);    // 返回 4
 * */
public class LRUCache {
    static class Node {
        int key;
        int val;
        Node next;
        Node prev;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return this.key == node.key;
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }

    }
    static class Cache {
        private Node head;
        private Node tail;
        private int capacity;
        private int size;
        Cache(Node head, Node tail, int capacity) {
            this.head = head;
            this.tail = tail;
            this.capacity = capacity;
            this.size = 0;
        }
        Cache(int capacity) {
            this(null,null, capacity);
        }
        boolean add(Node node) {
            if (size >= capacity) {
                return false;
            }
            Node newNode = node;
            if (size == 0) {
                head = newNode;
                tail = head;
            } else {
                head.prev = newNode;
                newNode.next = head;
                head = newNode;
            }
            size++;
            return true;
        }
        Node deLink(Node node) {
            if (node == head) {
                deLinkHead();
            } else if (node == tail) {
                deLinkTail();
            } else {
                Node prev = node.prev;
                Node next = node.next;
                node.prev = null;
                node.next = null;
                prev.next = next;
                next.prev = prev;
                size--;
            }
            return node;
        }

        Node deLinkHead() {
            Node oldHead = head;
            if (head != null) {
                Node newHead = head.next;
                head.next = null;
                head = newHead;
                if (newHead == null) {
                    tail = null;
                } else {
                    newHead.prev = null;
                }
                size--;
            }
            return oldHead;
        }
        Node deLinkTail() {
            Node oldTail = tail;
            if (tail != null) {
                Node newTail = tail.prev;
                tail.prev = null;
                tail = newTail;
                if (tail == null) {
                    head = null;
                } else {
                    tail.next = null;
                }
                size--;
            }
            return oldTail;
        }


    }
    Map<Integer, Node> nodeTables;
    Cache cache;
    public LRUCache(int capacity) {
        nodeTables = new HashMap<>();
        cache = new Cache(capacity);
    }

    public int get(int key) {
        if (!nodeTables.containsKey(key)) {
            return -1;
        }
        Node node = nodeTables.get(key);
        int ans = node.val;
        updateCache(node);
        return ans;
    }

    public void put(int key, int value) {
        if (nodeTables.containsKey(key)) {
            Node node = nodeTables.get(key);
            node.val = value;
            updateCache(node);
            return;
        }
        Node node = new Node();
        node.key = key;
        node.val = value;
        nodeTables.put(key, node);
        if (!cache.add(node)) {
            Node tail = cache.deLinkTail();
            nodeTables.remove(tail.key);
            cache.add(node);
        }
    }

    private void updateCache(Node node) {
        Node lastNode = cache.deLink(node);
        cache.add(lastNode);
    }



    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(1));
        lruCache.put(3,3);
        System.out.println(lruCache.get(2));
        lruCache.put(4,4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
    }


}
